Search results for "Computational problem"
showing 10 items of 13 documents
An autonomous petrological database for geodynamic simulations of magmatic systems
2022
SUMMARY Self-consistent modelling of magmatic systems is challenging as the melt continuously changes its chemical composition upon crystallization, which may affect the mechanical behaviour of the system. Melt extraction and subsequent crystallization create new rocks while depleting the source region. As the chemistry of the source rocks changes locally due to melt extraction, new calculations of the stable phase assemblages are required to track the rock evolution and the accompanied change in density. As a consequence, a large number of isochemical sections of stable phase assemblages are required to study the evolution of magmatic systems in detail. As the state-of-the-art melting diag…
Algebraic and logical characterizations of deterministic linear time classes
1997
In this paper an algebraic characterization of the class DLIN of functions that can be computed in linear time by a deterministic RAM using only numbers of linear size is given. This class was introduced by Grandjean, who showed that it is robust and contains most computational problems that are usually considered to be solvable in deterministic linear time.
Fast and Simple Approximation of the Diameter and Radius of a Graph
2006
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
MetNet: A two-level approach to reconstructing and comparing metabolic networks
2021
Metabolic pathway comparison and interaction between different species can detect important information for drug engineering and medical science. In the literature, proposals for reconstructing and comparing metabolic networks present two main problems: network reconstruction requires usually human intervention to integrate information from different sources and, in metabolic comparison, the size of the networks leads to a challenging computational problem. We propose to automatically reconstruct a metabolic network on the basis of KEGG database information. Our proposal relies on a two-level representation of the huge metabolic network: the first level is graph-based and depicts pathways a…
Randomized kernels for large scale Earth observation applications
2020
Abstract Current remote sensing applications of bio-geophysical parameter estimation and image classification have to deal with an unprecedented big amount of heterogeneous and complex data sources. New satellite sensors involving a high number of improved time, space and wavelength resolutions give rise to challenging computational problems. Standard physical inversion techniques cannot cope efficiently with this new scenario. Dealing with land cover classification of the new image sources has also turned to be a complex problem requiring large amount of memory and processing time. In order to cope with these problems, statistical learning has greatly helped in the last years to develop st…
Quantum Computation With Devices Whose Contents Are Never Read
2010
In classical computation, a "write-only memory" (WOM) is little more than an oxymoron, and the addition of WOM to a (deterministic or probabilistic) classical computer brings no advantage. We prove that quantum computers that are augmented with WOM can solve problems that neither a classical computer with WOM nor a quantum computer without WOM can solve, when all other resource bounds are equal. We focus on realtime quantum finite automata, and examine the increase in their power effected by the addition of WOMs with different access modes and capacities. Some problems that are unsolvable by two-way probabilistic Turing machines using sublogarithmic amounts of read/write memory are shown to…
Advanced Scatter Search for the Max-Cut Problem
2009
The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity prob…
Configuration Expansion by Means of Pseudonatural Orbitals
1977
The configuration interaction (CI) method as a general approach to solving the many-electron Schrodinger equation to—in principle—any desired accuracy, has been described in this volume by Shavitt. We refer to that chapter for all basic concepts of the CI method and an outline of its merits and its computational problems.
An Introduction to Computational Complexity
2016
This chapter is not strictly about algebra. However, this chapter offers a set of mathematical and computational instruments that will allow us to introduce several concepts in the following chapters. Moreover, the contents of this chapter are related to algebra as they are ancillary concepts that help (and in some cases allow) the understanding of algebra.
On the modern use of the bòvedas tabicadas
2009
The paper concerns the study of the so-called “bòvedas tabicadas” (i.e. thin vaults constituted by layers of “rasillas” suitably superimposed) based on the results obtained by specific experimental investigations effected on the material of which they are constituted as well as on a vault that is still working. In particular, aim of the present research is the implementation of a first analysis of the structure in its present configuration (often unusable), with the purpose to evaluate the real structure serviceability related to the prescribed intensity of the acting loads, and moreover the execution of a new second analysis of the same structure but suitably reinforced by placing further …